# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

import sys
import math
from random import uniform
from time import clock
import matplotlib.pyplot as plt

''' Class responsable for QuickSort algorithm and tests'''
class QuickSort:

    '''@param A: list to sort'''
    def quicksort(self, A, p, r):
        def partition(self, A, p, r):
            x = A[r]
            i = p - 1
            for j in range(p, r):
                if A[j] <= x:
                    i = i + 1
                    A[i], A[j] = A[j], A[i]
                    pass
                pass
            
            A[i + 1], A[r] = A[r], A[i + 1]

            return i + 1

        if p < r:
            q = partition(self,A, p, r)
            self.quicksort(A, p, q-1)
            self.quicksort(A, q+1, r)
            pass

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 25
        for n in Z:
            A = [ uniform(0.0,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = clock()
                self.quicksort(A, 0, len(A) / 2)
                t2 = clock()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct=20e6
        Z = [n**2/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Quick Sort")
        plt.legend()
        plt.show()

